//给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
//
//
// 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
//
//
// 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
//
// 以这种方式修改数组后，返回数组 可能的最大和 。
//
//
//
// 示例 1：
//
//
//输入：nums = [4,2,3], k = 1
//输出：5
//解释：选择下标 1 ，nums 变为 [4,-2,3] 。
//
//
// 示例 2：
//
//
//输入：nums = [3,-1,0,2], k = 3
//输出：6
//解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
//
//
// 示例 3：
//
//
//输入：nums = [2,-3,-1,5,-4], k = 2
//输出：13
//解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁴
// -100 <= nums[i] <= 100
// 1 <= k <= 10⁴
//
// Related Topics 贪心 数组 排序 👍 237 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.stream.IntStream;
import java.util.stream.Stream;

class MaximizeSumOfArrayAfterKNegations {
    public static void main(String[] args) {
        Solution solution = new MaximizeSumOfArrayAfterKNegations().new Solution();
        solution.largestSumAfterKNegations(new int[]{1, 3, 2, 6, 7, 9}, 3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    /*public int largestSumAfterKNegations(int[] nums, int k) {
        int result = 0;
        // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        for (int i = 0; i < nums.length; i++) {
            // 从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && k > 0) {
                nums[i] = Math.abs(nums[i]);
                k--;
            }
        }
        if (k % 2 == 1) nums[nums.length - 1] = 0 - nums[nums.length - 1];    // 如果K还大于0，那么反复转变数值最小的元素，将K用完
        // 求和
        for (int i : nums) {
            result += i;
        }
        return result;
    }*/

        /*public int largestSumAfterKNegations(int[] A, int K) {
            if (A.length == 1) return K % 2 == 1 ? -A[0] : A[0];
            Arrays.sort(A);
            int index = 0;
            for (int i = 0; i < K; i++) {
                // 如果为负数，那就变为相反数
                if (i < A.length - 1 && A[index] < 0) {
                    A[index] = -A[index];
                    // 如果变化之后大于等于后边数的绝对值，那么index++
                    // [1,3,2,6,7,9]
                    // 3
                    // 注意需要判断，否则全为正数就会不满足贪心
                    if (A[index] >= Math.abs(A[index + 1])) index++;
                    // 下一步不执行了
                    continue;
                }
                // 最终负数消耗完了，但是还有正数，所以一直利用最小的一个正数，把k消耗完
                A[index] = -A[index];
            }

            // 统计总和
            int sum = 0;
            for (int i = 0; i < A.length; i++) {
                sum += A[i];
            }

            return sum;
        }*/

        /*public int largestSumAfterKNegations(int[] A, int K) {
            Arrays.sort(A);
            int i = 0;
            for (; i < K; i++) {
                if (i < A.length && A[i] <= 0) {
                    A[i] = -A[i];
                } else break;
            }

            int j = K - i;
            if (j % 2 != 0) {
                Arrays.sort(A);
                A[0] = -A[0];
            }

            int sum = 0;
            for (int i1 : A) {
                sum += i1;
            }

            return sum;
        }*/

        public int largestSumAfterKNegations(int[] A, int K) {
            int n = A.length;
            Integer[] arr = new Integer[n];
            for (int i = 0; i < n; i++) {
                arr[i] = A[i];
            }

            Arrays.sort(arr, (o1, o2) -> Math.abs(o2) - Math.abs(o1));

            for (int i = 0; i < arr.length; i++) {
                if (arr[i] < 0 && K > 0) {
                    arr[i] = -arr[i];
                    K--;
                }
            }

            if (K % 2 != 0) arr[arr.length - 1] = -arr[arr.length - 1];

            int res = 0;
            for (Integer v : arr) {
                res += v;
            }

            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
